SAE202 : Exploration algorithmique d'un problème
Par SOUPRAMANIANE Cyril & NEJJARI Abdenour

Dans le cadre de la SAE202 : Exploration algorithmique d'un problème. Il nous a été demandé de réaliser un projet mathématique et informatique. </br> Après concertation avec notre enseignant, nous avons choisi de réaliser le projet Optimisation : Dichotomie.

Niveau : ☆

Description : Nous avons vu en cours que la méthode de la dichotomie est une méthode
permettant de déterminer l'extrema(local) d'une fonction sur un intervalle donné, c'est à dire la valeur de x à laquelle f(x) s'annule.

Animation : Les différentes étapes de l'algorithme sur trois fonctions différentes.

Nous avons travailler environ 16h sur ce projet et avons réparti le travail comme suit :

Malgré cette division, nous avons participé collègialement à l'intégralité du projet et échanger chacun avec l'autre au travers d'un canal discord privé crée spécialement pour ce travail et par mail.

Les bibliothèques

Voici les bibliothèques dont nous aurons besoin pour le bon fonctionnement de nos programmes de cette SAE.

Les programmes

Voici les programmes dont nous aurons besoin pour réaliser notre SAE à bien et obtenir les animations attendues

Pour commencer, la dichotomie est une méthode pour trouver une solution approchée à une équation f(x)=0 d'une fonction en répétant des partages d'un intervalle en deux parties puis en sélectionnant le sous-intervalle dans lequel existe le zéro de la fonction.

On considère deux nombres réels a et b et une fonction réelle f continue sur l'intervalle [a, b] telle que f(a) et f(b) soient de signes opposés.

Supposons que nous voulions résoudre l'équation f(x) = 0.

D'après le théorème des valeurs intermédiaires, f a au moins un zéro dans l’intervalle [a, b].

Pour trouver la solution, on divise l'intervalle en deux parties égales avec comme milieu m=(a+b)/2. Il y a maintenant deux possibilités : soit f(a) et f(m) sont de signes contraires, soit f(m) et f(b) sont de signes contraires.

Si f(a)×f(m) on le même signe, la solution se trouve alors dans l'encadrement [m,b] sinon elle se trouve dans l'encadrement [a,m].

On recommence alors la recherche dans le nouveau l'encadrement jusqu'à ce que a−b soit inférieur à la précision souhaiter.

On développe donc la fonction ci-dessous:

Les différents types de fonction

Nous allons tester la méthode de dichotomie sur plusieurs types de fonction.

En effet, certaines fonctions sont monotones donc n'ont aucune solution à f(x)=0.

D'autres ont une solution car elles ont qu'un changement de signe. Et enfin, d'autres ont en plusieurs car plusieurs changements du signes.

Les fonctions à plusieurs solutions

On affecte une fonction mathématique à la fonction dichotomie afin de trouver la valeur de x en laquelle f(x) s'annule.

On cherche à résoudre f(x)=0 avec : f(x)=5x^2−34.

On définit la fonction f(x) dans python.

On trace le graphique de la fonction afin de visualiser sa courbe et de déterminer le nombre de changements de signes qui nous donnera implicitement le nombre de solutions à f(x)=0. On peut donc en apercevoir deux sur cette courbe.

Determination des intervalles de la fonction à plusieurs solutions

On peut voir sur le graphe que la fonction admet deux solutions. On va alors chercher les solutions dans les deux intervalles [-4,-1] et [1,4] en utilisant la méthode de recherche par dichotomie.

ATTENTION: CERTAINS FONCTIONS SONT MONOTONES ET N'ONT DONC PAS DE SOLUTIONS. IL FAUDRA DONC VÉRIFIER QUE LA/LES INTERVALLES EN QUESTION CONTIENNENT UN/DES SOLUTIONS À f(x)=0.

Placement du premier intervalle sur un graphique

On peut voir sur le graphe que la fonction admet deux solutions. On va alors chercher la première solution à f(x) = 0 dans l'intervalle [-4,-1] en utilisant la méthode de recherche par dichotomie.

Determination de la première solution

On cherche à déterminer la première solution à f(x)=0 à travers l'exécution de la fonction dichotomie.

Placement de la première solution sur un graphique

On va, ensuite, placer la première solution sur la courbe.

Placement du deuxième intervalle sur un graphique

On réitère l'opération avec le deuxième intervalle en placant déjà le deuxième intervalle.

Determination de la deuxième solution

On va, ensuite, déterminer la deuxième solution qui annule la fonction f(x) en 0 par le biais de la fonction dichotomie.

Placement de la deuxième solution sur un graphique

Puis, enfin, on va placer la deuxième et dernière solution de cette fonction sur la courbe

Placement des deux solutions sur un graphique

On va retracer la courbe en entière avec les deux solutions placées sur cette dernière pour avoir un meilleur visuel sur l'ensemble de la fonction.

Les animations de f(x)=5*x**2-34

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons pour la fonction f(x)=5*x**2-34.

Les fonctions à une seule solution dans l'intervalle de gauche

On affecte une fonction mathématique à la fonction dichotomie afin de trouver la valeur de x en laquelle f(x) s'annule.

On cherche à résoudre y(x)=0 avec : y(x)=5x+4.

On définit la fonction y(x) dans python.

On trace le graphique de la fonction afin de visualiser sa courbe et de déterminer le nombre de changements de signes qui nous donnera implicitement le nombre de solutions à y(x)=0.

Determination de l'intervalle de la fonction à une solution dans l'intervalle de gauche

On peut voir sur le graphe que la fonction admet une solution. On va alors chercher la solution dans l'intervalle de gauche[-4,0] en utilisant la méthode de recherche par dichotomie.

ATTENTION: CERTAINS FONCTIONS SONT MONOTONES ET N'ONT DONC PAS DE SOLUTIONS. IL FAUDRA DONC VÉRIFIER QUE LA/LES INTERVALLES EN QUESTION CONTIENNENT UN/DES SOLUTIONS À y(x)=0.

Placement de l'intervalle de gauche sur un graphique

On peut voir sur le graphe que la fonction admet une seule solution. On va alors chercher la solution à f(x) = 0 dans l'intervalle [-4,0] en utilisant la méthode de recherche par dichotomie. Tout d'abord, plaçons l'intervalle (de gauche) qui contient la seule solution de la fonction à y(x)=0.

Determination de la solution

Puis, determinons la valeur de l'unique solution à y(x)=0 à l'aide de la fonction dichotomie.

Placement de la solution sur un graphique

Enfin, plaçons l'unique solution sur son intervalle (de gauche) en premier temps. Puis dans un second temps, plaçons la sur la coube complète pour un meilleur aperçu.

Les animations de y(x)=5*x+4

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons pour la fonction y(x)=5*x+4.

Les fonctions à une seule solution dans l'intervalle de droite

On affecte une fonction mathématique à la fonction dichotomie afin de trouver la valeur de x en laquelle f(x) s'annule.

On cherche à résoudre z(x)=0 avec : z(x)=-3x+2.

On définit la fonction z(x) dans python.

On trace le graphique de la fonction afin de visualiser sa courbe et de déterminer le nombre de changements de signes qui nous donnera implicitement le nombre de solutions à z(x)=0.

Determination de l'intervalle de la fonction à une solution dans l'intervalle de droite

On peut voir sur le graphe que la fonction admet une solution. On va alors chercher la solution dans l'intervalle de gauche[-4,0] en utilisant la méthode de recherche par dichotomie.

ATTENTION: CERTAINS FONCTIONS SONT MONOTONES ET N'ONT DONC PAS DE SOLUTIONS. IL FAUDRA DONC VÉRIFIER QUE LA/LES INTERVALLES EN QUESTION CONTIENNENT UN/DES SOLUTIONS À z(x)=0.

Placement de l'intervalle de droite sur un graphique

On peut voir sur le graphe que la fonction admet une unique solution. On va alors chercher la solution à f(x) = 0 dans l'intervalle [0,4] en utilisant la méthode de recherche par dichotomie.Plaçons déjà l'intervalle (de droite) qui contient l'unique solution de la fonction z(x)=0.

Determination de la solution

Ensuite, dans un second temps, determinons ensemble la valeur de la solution z(x)=0 grâce à la dichotomie.

Placement de la solution sur un graphique

Puis, dans un dernier temps, plaçons cette solution sur l'intervalle (de droite) qui le contient. Mais également sur la courbe au complète pour un meilleur aperçu.

Les animations de z(x) = -3*x+2

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons pour la fonction z(x)=-3*x+2.

Les animations des trois fonctions en même temps

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons qui combinent les trois fonctions que nous avons usé pour cette SAE afin de voir la différence entre ces dernières.

Les limites de la méthode de dichotomie
Le principal avantage de cette méthode est sa robustesse, puisque si f est continue, alors l'algorithme est théoriquement convergent (la taille de l'intervalle de recherche tend vers zéro). Le principal défaut de l'algorithme est que seul le signe de f est utilisé, ce qui mène à une convergence plutôt lente, c'est-à-dire quasiment linéaire. La méthode de Newton, qui utilise la valeur de f ainsi que la valeur de la pente de f, est, quand elle converge, bien plus rapide.
Cette méthode d'une grande solidité nécessite cependant de connaître à chaque étape le signe de f(m). Dans quelques cas, il peut arriver que la valeur de f(m) soit si proche du 0 que le logiciel de calcul ne permette plus de déterminer le signe de f(m) (il assimile f(m) à 0). L'algorithme risque alors de conduire à l'élimination d'une moitié de l'intervalle et à la convergence vers une valeur éloignée de la solution. D'une manière plus générale, la détermination du signe de f(m) peut se révéler très difficile voire impossible, même en augmentant la précision du calcul du logiciel.
Cependant, aucune méthode n'est pas défaillante. Elles ont tous des avantages et inconvénients donc nous ne pouvons pas mettre un terme à ce problème.
Merci de votre attention. Nous arrivons à terme de ce projet dont nous avons mis énormèment de temps mais également d'effort à le réaliser. Ce ne fut pas une partie de plaisir mais ce fut très intéressant et ludique. Nous avons appris beaucoup de choses à travers ce projet, et nous espérons en apprendre davantage.